package kmp;

public class Test03 {
    static String T = "abaaefagedabaabcaedff";
    static String P = "abaabca";

    static int[] next = new int[100005];

    static void Getnext(String p) {
        int k = -1;
        int j = 0;
        int len = p.length();
        next[0] = -1;
        while(j < len - 1){
            if(k == -1 || p.charAt(k) == p.charAt(j)){
                k++;
                j++;
                next[j] = k;
            }else{
                k = next[k];
            }
        }
    }

    static int KMP(int sStart, String s, String p) {
        /*

        tStart 从主串的哪个位置开始，从头开始为0

        s 主串

        p 模式串

        */
        int i = sStart; //从主串的sStart位置开始

        int j = 0;

        int sLen = s.length();

        int pLen = p.length();

        while (i < sLen && j < pLen) {
            //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j == -1 || s.charAt(i) == p.charAt(j)) {
                i++;         //继续对下一个字符比较
                j++;         //模式串向右滑动
            } else {
                j = next[j];
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = nextt[j]
                //nextt[j]即为j所对应的nextt值
            }
        }
        if (j == pLen)
            return (i - j);     //主串中存在该模式返回下标号

        else
            return -1;     //主串中不存在该模式
    }


    public static void main(String[] args) {
        Getnext(P);
        System.out.println(KMP(0, T, P));
    }
}
